package main

// 739. 每日温度
func main() {
	temperatures := []int{73, 74, 75, 71, 69, 72, 76, 73}
	ints := dailyTemperatures(temperatures)
	for _, i := range ints {
		println(i, ",")
	}
}

func dailyTemperatures2(temperatures []int) []int { // 2025.02.23 练习, 模拟递归
	numsLen := len(temperatures)
	var stack []int
	ans := make([]int, numsLen)

	for idx, tmp := range temperatures {
		for len(stack) > 0 && temperatures[stack[len(stack)-1]] < tmp {
			ans[stack[len(stack)-1]] = idx - stack[len(stack)-1]
			stack = stack[:len(stack)-1]
		}
		stack = append(stack, idx)
	}

	return ans
}

func dailyTemperatures(temperatures []int) []int {
	// 单调栈，等于是所有前面的数在栈里面等爹，等到了就滚出去
	var stack []int
	ans := make([]int, len(temperatures))

	for i := 0; i < len(temperatures); i++ {
		// 逐个往前找把小于我的都弄出去
		for len(stack) > 0 && temperatures[stack[len(stack)-1]] < temperatures[i] {
			ans[stack[len(stack)-1]] = i - stack[len(stack)-1]
			stack = stack[:len(stack)-1]
		}
		// 没有小于我的了，那我自己进去了
		stack = append(stack, i)
	}
	return ans
}

// 使用动态规划，从后往前
func dailyTemperaturesByDp(temperatures []int) []int {
	// 使用动态规划，从后往前
	ans := make([]int, len(temperatures))

	// 动态转移方程，从后往前

	ans[len(temperatures)-1] = 0

	for i := len(temperatures) - 2; i >= 0; i-- {
		nextPoint := i + 1
		for temperatures[i] >= temperatures[nextPoint] {
			if ans[nextPoint] == 0 { // 不会更高了
				break
			}
			nextPoint = nextPoint + ans[nextPoint]
		}
		if temperatures[i] < temperatures[nextPoint] {
			ans[i] = nextPoint - i
		} else {
			ans[i] = 0
		}
	}

	return ans
}

// 给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。
//
//示例 1:
//
//输入: temperatures = [73,74,75,71,69,72,76,73]
//输出: [1,1,4,2,1,1,0,0]
//示例 2:
//
//输入: temperatures = [30,40,50,60]
//输出: [1,1,1,0]
//示例 3:
//
//输入: temperatures = [30,60,90]
//输出: [1,1,0]
//
//提示：
//
//1 <= temperatures.length <= 105
//30 <= temperatures[i] <= 100
